package Demo2_9;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-09
 * Time:18:06
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class LowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为空，或者根节点就是 p 或 q 中的一个，直接返回根节点
        if (root == null || root == p || root == q) {
            return root;
        }
        // 递归遍历左子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 递归遍历右子树
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果左子树和右子树都不为空，说明 p 和 q 分别在左右子树中，当前根节点就是最近公共祖先
        if (left != null && right != null) {
            return root;
        }
        // 如果左子树不为空，说明 p 和 q 都在左子树中，返回左子树的结果
        return left != null ? left : right;
    }

    public static void main(String[] args) {
        // 构建一个简单的二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        LowestCommonAncestor solution = new LowestCommonAncestor();
        // 找到节点 5 和节点 1 的最近公共祖先
        TreeNode p = root.left; // 节点 5
        TreeNode q = root.right; // 节点 1
        TreeNode ancestor = solution.lowestCommonAncestor(root, p, q);
        System.out.println("节点 " + p.val + " 和节点 " + q.val + " 的最近公共祖先是: " + ancestor.val);

        // 找到节点 5 和节点 4 的最近公共祖先
        p = root.left; // 节点 5
        q = root.left.right.right; // 节点 4
        ancestor = solution.lowestCommonAncestor(root, p, q);
        System.out.println("节点 " + p.val + " 和节点 " + q.val + " 的最近公共祖先是: " + ancestor.val);
    }
}
